import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

import java.util.*;

public class test {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    // 用于存储 inOrder 数组中每个元素的索引
    private Map<Integer, Integer> inOrderIndexMap = new HashMap<>();

    public int[] solve(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return new int[0];
        }
        // 初始化哈希表
        for (int i = 0; i < inOrder.length; i++) {
            inOrderIndexMap.put(inOrder[i], i);
        }
        TreeNode root = reConstructTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
        ArrayList<Integer> tmp = rightSideView(root);
        int[] res = new int[tmp.size()];
        for (int i = 0; i < tmp.size(); i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }

    // 层序遍历
    public ArrayList<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) {
            q.offer(root);
        }
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- != 0) {
                TreeNode tmp = q.poll();
                if (tmp.left != null) {
                    q.offer(tmp.left);
                }
                if (tmp.right != null) {
                    q.offer(tmp.right);
                }
                // 最右元素
                if (size == 0) {
                    res.add(tmp.val);
                }
            }
        }
        return res;
    }

    public TreeNode reConstructTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        // 先把根节点保存一下
        TreeNode root = new TreeNode(preOrder[preStart]);
        // 在 inOrder 中找到根节点的位置
        int rootIndexInOrder = inOrderIndexMap.get(preOrder[preStart]);
        // 计算左子树的节点数量
        int leftSubtreeSize = rootIndexInOrder - inStart;
        // 递归构建左子树
        root.left = reConstructTree(preOrder, preStart + 1, preStart + leftSubtreeSize, inOrder, inStart, rootIndexInOrder - 1);
        // 递归构建右子树
        root.right = reConstructTree(preOrder, preStart + leftSubtreeSize + 1, preEnd, inOrder, rootIndexInOrder + 1, inEnd);
        return root;
    }
}